The present invention relates to a method of enabling a plurality of data objects to be read consistently in a database.
The invention can be applied to particular benefit in databases where transactions are managed with the aid of two-phase locking, wherein a first phase comprises a request for access to objects affected by the transaction and locking of these objects as soon as access has been obtained, and wherein a second phase comprises commitment of the transaction and the release of all locks that were set in the first phase.
Transaction management is a fundamental technique in database management processes and is sometimes used to isolate a transaction from other actions or events in the database and to provide a consistent picture of the information contained in a dynamic and changing database.
In the case of a traditional transaction process, those objects used by the transaction during the actual transaction process are blocked so as to prevent their use by other transactions during an ongoing transaction. Other transactions that desire access to the same objects must therefore either wait or abort and try again later on.
The actual work carried out in a transaction includes actions that change an object and/or actions that leave an object unchanged, these actions, or events, being referred to hereinafter as object changing events and object non-changing events. The content of an object can be changed, or updated, by writing the changed content into a new version of the object, or by writing over the old version.
In known techniques, all actions concerning a transaction, both a changing and a non-changing transaction, are carried out prior to xe2x80x9ccommitmentxe2x80x9d of the transaction. The term xe2x80x9ccommit/commitmentxe2x80x9d of a transaction is well known to the person skilled in this art, and means in simple terms that the transaction informs that the actions or events requested by the transaction and requiring isolation have been carried out. It can also be mentioned that the term commit also typically includes the release of all locks that have been set, although we speak about the release of locks as a separate action in the present document.
The current or existing version of the object prior to the transaction is retained in this current form until no further transactions use that current or existing version any longer. This means that different versions of an object may need to be saved for periods of different duration, depending on which transactions use the versions in question.
Certain applications require access to a database in real time, in a manner which will not block access to objects used with other transactions, particularly with regard to purely reading transactions. It is known in this context to use a database management system that permits access to different objects that are not transaction-bound and that, on the contrary, are fast and non-blocking.
The drawback with such systems is that the user acting in the database cannot proceed in the same isolated manner as that which is possible in a transaction-bound system and cannot be provided with a guaranteed consistent picture of the database.
It is also known that non-blocking transactions can be achieved by managing a well-defined transaction protocol. These transaction protocols, however, are not easily managed and their implementation is complex, process-demanding and/or require a large memory capacity.
Thus, it is known either to provide a database that can be implemented quickly and simply but which will not always be able to guarantee a consistent picture of the database, in other words correct result, or to provide a database that while being management positive and showing a correct picture is both slow and ponderous in use.
Databases that are based on so-called optimistical control of concurrent transactions where no locks are used are also known to the art. This control is based on allowing all transactions with the assumption that no conflict will occur.
More specifically, an optimistical control of concurrent transactions means that a check is made to ensure that no conflicts will occur in conjunction with a transaction prior to the transaction being xe2x80x9ccommittedxe2x80x9d. If a conflict is found to exist, the transaction is aborted. Otherwise, commitment of the transaction is allowed. It should also be mentioned that two different locks are usual in so-called two-phase locking, or locking in two phases.
A first lock is a so-called shared lock which is set by purely reading transactions with regard to a data object and which allows other reading transactions to have access to said object, but which locks the object to changing transactions.
A second lock is a so-called exclusive lock which is set by transactions that change the data object and which locks the object with regard to all other transactions.
The following publications disclose examples of earlier known techniques, in which different types of non-blocking transactions are exemplified.
This publication describes a database where an index covering the various objects it the database shows where the different objects are found. When an object-changing transaction is started, the transaction is referred to a new position in the database in which the changed objects shall be stored. A new index that points to the new positions of the changed objects is created.
The old index is retained and still points to the old positions of respective objects.
Each version of an earlier index is kept alive for as long as some transaction uses this version of the index.
Although this transaction management provides a non-blocking transaction protocol, it requires a large amount of memory space, since several different versions of the index can exist in parallel. Implementation of the transaction management is also relatively complex.
This publication describes the introduction of three new types of lock, to wit cash lock, pending lock and out-of-date lock. When a first transaction, a reading transaction, sets a lock on different objects, a cash lock is set instead of a shared lock. If a second transaction requests an exclusive lock on the same objects whilst the first transaction is still in process, the cash lock is changed to a pending lock.
If the second transaction changes an object with a pending lock, the lock is changed to an out-of-date lock. If the second transaction makes no change in an object, the pending lock is changed to a cash lock when the second transaction is committed.
The first transaction normally continues as long as all locks are cash locks. If any pending lock exists on any of the objects that are affected by the first transaction, the first transaction waits until the pending lock switches to some other lock.
The first transaction can continue when a pending lock changes to a cash lock. If the pending lock changes to an out-of-date lock, this indicates that the object has been changed and the first transaction is subsequently aborted.
Although this method enables a lock to be set that does not block changing transactions, it necessitates the abortion of a commenced reading transaction due to a data object changing transaction having changed an object whilst performing the reading transaction.
Technical Problems
When considering the earlier standpoint of techniques as described above, it will be seen that a technical problem resides in enabling transaction management in which the time period over which an allocated lock blocks an object changing transaction to be greatly shortened.
Another technical problem is one of shortening the time period between setting an allocated lock and releasing said lock for a non-changing transaction.
A further technical problem is one of providing unlimited access to objects used by a non-changing transaction with respect to time, without blocking objects affected by changing transactions during this access time, i.e. a non-blocking access after a lock set by the transaction has been released.
It will also be seen that a technical problem resides in dividing a transaction into changing and non-changing actions, in which an exclusive lock is provided for the changing actions in said transaction, and a non-blocking, unlimited in time, access to affected objects is provided for the non-changing actions.
Another technical problem is one of solving the aforedescribed technical problems in a database that is based on that each version of an object is allocated a counter which is incremented when a transaction is allowed access to the object, such as when setting a lock, and is decremented when a transaction no longer requires access to this version of the object, such as when releasing a lock.
A further technical problem is one of solving the earlier described technical problems in a database that is based on allocating to each transaction a time stamp which indicates the time at which the transaction was commenced, where each transaction stamps a version of respective affected objects with its time stamp when no younger transaction has time-stamped this version of the object, and where each version of an object shall be retained for as long as no transaction has been terminated as an older transaction, or is equally as old as the youngest time stamp that has been allocated to the version in question.
Solution
The present invention takes as its starting point a method of enabling a plurality of objects to be read consistently in a database in which transactions are managed by locking in two phases.
A first phase includes a request for access to the object affected by the transaction and for the objects to be locked after access has been obtained thereto, and a second phase which includes committing the transaction and the release of all locks set in the first phase.
The actual work performed in the transaction may include actions that change an object and/or actions that do not change an object, wherein updating or changing of the content of an object is effected by writing the changed content to a new version of the object, and wherein the version of the object that existed prior to the transaction is retained until no further transactions use the existing, or current, version.
The transaction performs all data changing actions in the first phase.
With a starting point from such a method and with the object of providing a solution to one or more of the aforesaid technical problems, it is proposed in accordance with tile present invention that the transaction retains access to said objects after the second phase, that the transaction performs the greatest possible number of non-changing actions after the second phase, and that the transaction closes access to the objects after performing said non-changing actions.
Subsequent to the release of said locks, the transaction thus retains consistent snapshots of affected objects within the database with respect to non-changing actions.
It is also proposed in accordance with the invention that after the second phase the access to an object will include marking respective objects in a current version as being used by the transaction, and that closing of access to the objects comprises removing said mark, therewith keeping the version of said object alive despite the transaction being committed, at least until the transaction is closed.
When each version of an object is allocated a counter which increments, steps up, when a transaction has been allocated access to said version, such as when setting a lock, and decremented, stepped down, when a transaction no longer needs access to said version, such as when releasing a lock, the present invention teaches that said mark consists in decrementation of the counter solely when the mark is removed, i.e. when closing the transaction.
When each transaction is allocated a time stamp that indicates the time at which the transaction was commenced, where each transaction stamps respective versions of affected objects with its time stamp when no younger transaction has time-stamped this version of the object, and where each version of an object is allowed to remain provided that no transaction which is older than or equally as old as the youngest time-stamp allocated to said version has still not been terminated, it is proposed in accordance with the invention that said mark comprises the time stamp of the version of respective objects, and that the transaction is considered to have been terminated when closing access to said object.
When the transaction solely includes non-changing actions, it is proposed in accordance with the invention that the lock will comprise a shared lock that will enable other transactions to obtain access to an object prior to the shared lock being released, but with the limitation of being able to only read the object.
With the intention of providing a so-called group opening, where all objects to be opened are known prior to commencement of the transaction, it is proposed in accordance with the present invention that the objects are opened in the first phase.
With the intention of providing so-called recursive opening of data objects, where one or more start objects is/are known prior to commencing the transaction, and where one or more of said start objects refers/refer to one or more further objects, it is proposed in accordance with the present invention that the start object(s) is/are opened in the first phase, that an evaluation of any references to further objects is made in the first phase, and that any further objects are opened in the first phase.
It is also proposed in accordance with the present invention that any references from any further objects to yet further objects are evaluated in the first phase, that any still further objects are opened in the first phase, and so on.
The present invention also enables the number of available objects to be limited, by predetermining the number of permitted levels of objects deriving from references to further objects from earlier opened objects.
With the intention of providing a so-called path opening, wherein one or more start objects is/are known prior to commencing the transaction, and wherein one or more of the start objects refers/refer to one or more further objects, it is proposed in accordance with the invention that the start object(s) is/are opened in the first phase, that any references to further objects are evaluated in the first phase with respect to a predetermined object of said start objects, and that any further objects are opened in the first phase.
According to one embodiment of the invention, any references from possible further objects to still further objects are evaluated in the first phase, and any still further objects are opened in the first phase, and so on.
According to another embodiment, the number of objects available is limited by allowing the number of permitted levels of objects deriving from references to further objects from earlier opened objects to be predetermined.
Advantages
Those advantages primarily afforded by an inventive method reside in a method which enables the time during which a transaction locks an object against access by other transactions to be shortened, therewith enabling reading transactions of a virtually non-blocking nature to be effected in a simple, fast, relatively memory-lean and calculation-beneficial manner.
The method provides a retained consistent snapshot of an object affected by a transaction after the transaction has been committed, therewith enabling the transaction to use the consistent picture of the object for non-changing actions without limiting the transaction with respect to time and without blocking other transactions.
The time period over which other transactions lock one or more objects, i.e. even transactions that are not purely reading transactions, can be shortened to different extents, meaning that a database will have different degrees of speeds for all transactions, since the waiting times for locked objects will be significantly shortened.
The present invention also provides a particularly advantageous method in databases where copying of different object versions is considered to be an expensive operation with respect to memory capacity, time and/or execution. According to one embodiment of the inventive method, copying is avoided primarily for reading transactions and permits earlier release of used locks with regard to time.
The present invention is also particularly advantageous in respect of databases where a need for consistent snapshots of a number of objects is found, but where this picture need not necessarily be fully updated in accordance with the latest transactions.
The invention is also particularly advantageous in respect of implementation within RAM databases where high requirements are found in connection with real time applications.
The primary characteristic features of an inventive method are set forth in the characterising clause of the following claim 1.